The person skilled in the art understands the term "condensation" to designate a non-falsifiable transformation of an initial digital data sequence into a resulting condensed digital data block. The term "condensed" can be explained by the fact that the resulting condensed digital data block is much shorter than the initial digital data sequence.
The transformation is said to be non-falsifiable (or anti-collision) when it is not possible in practice with the calculation means actually available to discover two different digital data sequences that lead to the same condensed block and thus, in particular, given a first digital data sequence, to find a second digital data sequence distinct from the first sequence and producing the same condensed block.
In general, the person skilled in the art uses the anti-collision property of the condensation transformation to protect the integrity of digital data, and in particular to detect anomalies (changes, inversions, omissions, or additions of digital data) that may be of accidental origin (hardware errors) or of deliberate origin (deliberate fraudulent manipulations) to which the digital data may be subject. For example, for computer files stored on some medium, the person skilled in the art calculates the condensed block of the computer file to be protected and stores said condensed block in non-volatile memory. Each time the computer file is reused, the person skilled in the art calculates its condensed block again and then compares it with the condensed block as previously stored. The result of the comparison serves in theory to determine whether anomalies exist in the computer file to be protected.
Digital data may also be condensed for the purpose of signing computer messages. In this case the message to be signed is initially condensed and then a signature function making use of a secret is applied to the condensed block.
At present, digital data condensing operations are performed on the basis of encrypting algorithms such as the "Data Encryption Standard" (DES) algorithm in which the one-way dependence property on the encryption key confers the anti-collision property to the operation of condensing digital data.
The drawback of such encryption algorithms is the slowness with which they are performed when implemented purely in software.
In the document "Design Principles For Hash Functions" by I. B. Damgard, Proceeding of Crypto 89, Aug. 1989, a solution is proposed for constructing a condensation function operating on a digital data sequence of arbitrary size on the basis of elementary anti-collision functions operating on digital data blocks of fixed size, namely "hash functions". More precisely, that document suggests using schemes for calculating condensed blocks that are of the type suitable for being performed in parallel, being broken down into a plurality of calculation modules each performing an elementary anti-collision function. However, that document does not describe any effective construction for performing an elementary anti-collision operation, both quickly and efficiently for the purpose of condensing digital data.
The present invention seeks specifically to provide a solution to this problem.
A first aim of the invention is to provide a device for condensing digital data which is based on tools that are fast and simple, such as tables and logic operators.
Another aim of the invention is to provide a data condensation device for digital data sequences of arbitrary length.
Yet another aim of the invention is to apply the data condensation device to devices that are intended to protect the integrity of digital data, such as certification devices or electronic signature devices.